home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor1 / prime2.doc < prev    next >
Text File  |  1995-03-31  |  3KB  |  77 lines
  1. (Comp.sys.handhelds) 
  2. Item: 1375 by kskalb at faui1f.informatik.uni-erlangen.de 
  3. Author: [Klaus Kalb] 
  4.   Subj: HP48: primality testing 
  5.   Date: Fri Dec 07 1990 07:56  
  6.  
  7. This program for the HP48 tests numbers for being prime. 
  8. It is written as a user defined function, so you can include 
  9. it into algebraics. 
  10.  
  11. Start it with a number (binary or real) in level 1 and it will answer: 
  12.  0 if the number is composite 
  13.  1 if the number is prime 
  14.  2 if it can't do the job  
  15.  
  16. The last case occurs only if the number is greater than 25*10^9. 
  17. Even if this occurs, you can be quite sure that the given number 
  18. is a prime, since the numbers that give a 2 on this test and are 
  19. composite are very rare --- but they do exist. 
  20. (they are indeed so rare that I don't know an example ;-) 
  21.  
  22. This test is fast --- testing a prime near 10^9 will take about 7000 ticks. 
  23. This is less then one second --- not so bad for a small machine. 
  24.  
  25. Of course this is accomplished using mcode. You need ASC\-> to get it 
  26. into your machine.  [already ASC'd; you don't need to.  -jkh-] 
  27.  
  28. ------------------------------------------------------------------------------ 
  29.  
  30. MORE ABOUT THE IMPLEMENTATION: 
  31.  
  32.   This program implements the test proposed by Pomerance, Selfridge and 
  33.   Wagstaff in _The_Pseudoprimes_to_25*10^9_ in math.comp.35 (1980) 
  34.  
  35.   Some special effort is made to recognize small primes and numbers with 
  36.   small factors on an early stage. 
  37.  
  38.   It will recognize all primes below 25*10^9. 
  39.  
  40.   It runs the strong pseudoprime test with the bases 2,3,5,7, so that 
  41.   a number passing this test with result 2 is at least a strong pseudoprime 
  42.   to these bases. 
  43.  
  44.   There are two subroutines written in mcode: 
  45.  
  46.     BGCD     calculates the greatest common divisor of two binary integers. 
  47.              It uses the binary algorithm that can be found in Knuth's 
  48.               _The_Art_of_Computer_Programming. 
  49.  
  50.     MILRAB   performs a strong pseudoprime test on the number N in level 2 
  51.              to the base B in level 1. It will accept any combination of 
  52.              binary integers and reals. The output is 1 if N is a 
  53.              strong base-B pseudoprime and 0 if not. 
  54.  
  55.   Both routines perform argument checking and give decent error messages. 
  56.  
  57. [The primality testing function itself is called 'PRIME?'.  -jkh-] 
  58.  
  59. ------------------------------------------------------------------------------ 
  60.  
  61. DISCLAIMER: (that's one I've found on the net ;-) 
  62.  
  63.      This program makes use of undocumented low-level features of 
  64.      the HP48SX calculator, and may or may not cause loss of data, 
  65.      excessive battery drainage, and/or damage to the calculator 
  66.      hardware.  The Author takes no responsibility whatsoever for  
  67.      any damage caused by the use of this program. 
  68.  
  69.      This software is provided "as is" and WITHOUT ANY EXPRESS OR 
  70.      IMPLIED WARRANTIES, including, but not limited to, THE IMPLIED 
  71.      WARRANTIES OF MERCHANTABILITY and FITNESS FOR A PARTICULAR PURPOSE. 
  72.  
  73. ------------------------------------------------------------------------------ 
  74.    Klaus Kalb    | mail :  IMMD1 / Martenstr. 3 / W-8520 Erlangen / Germany    
  75.                  | email:  kskalb@immd1.informatik.uni-erlangen.de    
  76. ------------------------------------------------------------------------------ 
  77.